#include <stdio.h>
#include <stdlib.h>
#include <string.h> // For strlen

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef int Status;

// ===== 运算符栈 (char) =====
typedef char SElemType_OPTR;
typedef struct
{
    SElemType_OPTR *base;
    SElemType_OPTR *top;
    int stacksize;
} SqStack_OPTR;

Status InitStack_OPTR(SqStack_OPTR *S)
{
    S->base = (SElemType_OPTR *)malloc(STACK_INIT_SIZE * sizeof(SElemType_OPTR));
    if (!S->base)
        exit(OVERFLOW);
    S->top = S->base;
    S->stacksize = STACK_INIT_SIZE;
    return OK;
}

Status Push_OPTR(SqStack_OPTR *S, SElemType_OPTR e)
{
    if (S->top - S->base >= S->stacksize)
    {
        S->base = (SElemType_OPTR *)realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(SElemType_OPTR));
        if (!S->base)
            exit(OVERFLOW);
        S->top = S->base + S->stacksize;
        S->stacksize += STACKINCREMENT;
    }
    *(S->top++) = e;
    return OK;
}

Status Pop_OPTR(SqStack_OPTR *S, SElemType_OPTR *e)
{
    if (S->top == S->base)
        return ERROR;
    *e = *--S->top;
    return OK;
}

SElemType_OPTR GetTop_OPTR(SqStack_OPTR S)
{
    if (S.top == S.base)
        exit(OVERFLOW);
    return *(S.top - 1);
}

// ===== 操作数栈 (int) =====
typedef int SElemType_OPND;
typedef struct
{
    SElemType_OPND *base;
    SElemType_OPND *top;
    int stacksize;
} SqStack_OPND;

Status InitStack_OPND(SqStack_OPND *S)
{
    S->base = (SElemType_OPND *)malloc(STACK_INIT_SIZE * sizeof(SElemType_OPND));
    if (!S->base)
        exit(OVERFLOW);
    S->top = S->base;
    S->stacksize = STACK_INIT_SIZE;
    return OK;
}

Status Push_OPND(SqStack_OPND *S, SElemType_OPND e)
{
    if (S->top - S->base >= S->stacksize)
    {
        S->base = (SElemType_OPND *)realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(SElemType_OPND));
        if (!S->base)
            exit(OVERFLOW);
        S->top = S->base + S->stacksize;
        S->stacksize += STACKINCREMENT;
    }
    *(S->top++) = e;
    return OK;
}

Status Pop_OPND(SqStack_OPND *S, SElemType_OPND *e)
{
    if (S->top == S->base)
        return ERROR;
    *e = *--S->top;
    return OK;
}

SElemType_OPND GetTop_OPND(SqStack_OPND S)
{
    if (S.top == S.base)
        exit(OVERFLOW);
    return *(S.top - 1);
}

// ===== 表达式求值核心函数 =====

char OP[] = {'+', '-', '*', '/', '(', ')', '#'};

int In(char c, char *op_set)
{
    for (int i = 0; op_set[i]; i++)
    {
        if (c == op_set[i])
            return TRUE;
    }
    return FALSE;
}

// 运算符优先级比较
// 返回值: > < =
char Precede(char op1, char op2)
{
    const char priority[7][7] = {
        //       +    -    *    /    (    )    #
        /* + */ '>',
        '>',
        '<',
        '<',
        '<',
        '>',
        '>',
        /* - */ '>',
        '>',
        '<',
        '<',
        '<',
        '>',
        '>',
        /* * */ '>',
        '>',
        '>',
        '>',
        '<',
        '>',
        '>',
        /* / */ '>',
        '>',
        '>',
        '>',
        '<',
        '>',
        '>',
        /* ( */ '<',
        '<',
        '<',
        '<',
        '<',
        '=',
        ' ',
        /* ) */ '>',
        '>',
        '>',
        '>',
        ' ',
        '>',
        '>',
        /* # */ '<',
        '<',
        '<',
        '<',
        '<',
        ' ',
        '=',
    };
    int i = -1, j = -1;
    for (int k = 0; k < 7; k++)
    {
        if (OP[k] == op1)
            i = k;
        if (OP[k] == op2)
            j = k;
    }
    if (i != -1 && j != -1)
    {
        return priority[i][j];
    }
    return ' '; // Error case
}

// 执行计算
int Operate(int a, char theta, int b)
{
    switch (theta)
    {
    case '+':
        return a + b;
    case '-':
        return a - b;
    case '*':
        return a * b;
    case '/':
        if (b != 0)
            return a / b;
        else
        {
            printf("Error: Division by zero!\n");
            exit(ERROR);
        }
    }
    return 0;
}

int EvaluateExpression(const char *exp)
{
    SqStack_OPTR OPTR;
    SqStack_OPND OPND;
    InitStack_OPTR(&OPTR);
    Push_OPTR(&OPTR, '#');
    InitStack_OPND(&OPND);

    int i = 0;
    while (exp[i] != '#' || GetTop_OPTR(OPTR) != '#')
    {
        if (exp[i] >= '0' && exp[i] <= '9')
        {
            int num = 0;
            while (exp[i] >= '0' && exp[i] <= '9')
            {
                num = num * 10 + (exp[i] - '0');
                i++;
            }
            Push_OPND(&OPND, num);
        }
        else
        {
            switch (Precede(GetTop_OPTR(OPTR), exp[i]))
            {
            case '<':
                Push_OPTR(&OPTR, exp[i]);
                i++;
                break;
            case '=':
            {
                char op;
                Pop_OPTR(&OPTR, &op);
                i++;
                break;
            }
            case '>':
            {
                char theta;
                int a, b;
                Pop_OPTR(&OPTR, &theta);
                Pop_OPND(&OPND, &b);
                Pop_OPND(&OPND, &a);
                Push_OPND(&OPND, Operate(a, theta, b));
                break;
            }
            }
        }
    }
    return GetTop_OPND(OPND);
}

int main()
{
    char expression[256];
    printf("请输入一个以'#'结尾的算术表达式 (例如: 7+(30+8)*5# ):\n");
    scanf("%s", expression);

    int result = EvaluateExpression(expression);

    printf("\n表达式 %s 的计算结果是: %d\n", expression, result);

    return 0;
}
